#ifndef PRIORITY_QUEUE_H_
#define PRIORITY_QUEUE_H_

#include <iostream>
#include <exception>

namespace mtm {

//declare all possible exceptions:
class ElementAlreadyExists: public std::exception {
};
class ElementDoesNotExist: public std::exception {
};
class IndexOutOfBounds: public std::exception {
};
class NoElements: public std::exception {
};

//declare a PriorityQueueElement<P,T> class:
template<class P, class T>
class PriorityQueueElement {
public:
	//the class'es fields:
	//the PriorityQueueElement's priority
	P priority;
	//the PriorityQueueElement's data
	T data;

	//constructs a PriorityQueueElement according to the given parameters
	PriorityQueueElement(const P& priority, const T& data) :
			priority(priority), data(data) {
	}

	/*
	 * comparison between 2 given PriorityQueueElements
	 * by both priority and data
	 */
	bool operator==(const PriorityQueueElement<P, T>& pqe) const;
	bool operator!=(const PriorityQueueElement<P, T>& pqe) const;
	//an helper function for printing a PriorityQueueElement
	friend std::ostream& operator<<(std::ostream& os,
			const PriorityQueueElement<P, T>& pqe) {
		return os << "[" << pqe.priority << "," << pqe.data << "]";
	}
};

//declare a PriorityQueue<P,T> class:
template<class P, class T>
class PriorityQueue {
	typedef PriorityQueueElement<P, T> Element;
	//an helper Node class (for the PriorityQueue's realization):
	class Node {
	public:
		//the class'es public field:
		//the node's data (holds a PriorityQueueElement<P,T>)
		Element pqe;

		//constructors and destructors:
		//an empty constructor for Node
		Node() {
		}
		//constructs a Node according to the given parameters
		Node(const P& priority, const T& data) :
				pqe(priority, data) {
		}
		
		//the class'es private field:
		//a pointer to the next node
		Node* next = NULL;
	};
public:
	//an helper Iterator class:
	class Iterator {
	public:
		//constructors and destructors:
		//an empty constructor for Iterator
		Iterator() :
				current(NULL) {
		}
		//constructs a Iterator according to the given parameters
		Iterator(Node* node) :
				current(node) {
		}
		
		friend bool operator==(const Iterator &a,
				const Iterator &b) {
			return a.current==b.current;
		}
		friend bool operator!=(const Iterator &a,
				const Iterator &b) {
			return !(a==b);
		}
		//returns the iterator's content
		Element& operator*() const {
			return current->pqe;
		}
		Element* operator->() const {
			return &current->pqe;
		}
		//returns an iterator which points to the next Node
		Iterator& operator++();
		//immediate ++ for Iterator (i++)
		Iterator operator++(int);
		//performs ++ 'num' times (according to the parameters)
		Iterator& operator+=(unsigned num);
		//returns an Iterator which equals to 'iter' + 'num'
		Iterator operator+(unsigned num) const;
		//cast to const_iterator
		operator typename PriorityQueue<P,T>::const_iterator() const {
			return current;
		}

	private:
		//the class'es field:
		//the current node it points on
		Node* current;
	};

	//an helper const_Iterator class:
	class const_iterator {
	public:
		//constructors and destructors:
		//an empty constructor for const_terator
		const_iterator() :
				current(NULL) {
		}
		//constructs a const_iterator according to the given parameters
		const_iterator(const Node* node) :
				current(node) {
		}
		
		friend bool operator==(const const_iterator &a,
				const const_iterator &b) {
			return a.current==b.current;
		}
		friend bool operator!=(const const_iterator &a,
				const const_iterator &b) {
			return !(a==b);
		}
		//returns the iterator's content
		const Element& operator*() const {
			return current->pqe;
		}
		const Element* operator->() const {
			return &(current->pqe);
		}
		//returns an iterator which points to the next Node
		const_iterator& operator++();
		//immediate ++ for Iterator (i++)
		const_iterator operator++(int);
		//performs ++ 'num' times (according to the parameters)
		const_iterator& operator+=(unsigned num);
		//returns an const_iterator which equals to 'iter' + 'num'
		const_iterator operator+(unsigned num) const;

	private:
		//the class'es field:
		//the current node it points on
		const Node* current;
	};

	//the main class PriorityQueue<P,T>:

	//constructors and destructors:
	//an empty constructor for PriorityQueue
	PriorityQueue() {}
	//copy constructor for PriorityQueue
	PriorityQueue(const PriorityQueue<P, T>& pq);
	//destructor for PriorityQueue
	~PriorityQueue() {
		this->clear();
	}

	//operator overloading:
	//assignment operator for PriorityQueue
	PriorityQueue<P, T>& operator=(const PriorityQueue<P, T>& pq);
	//random accessing to the PriorityQueue (returns the 'index' PQE in the PQ)
	//*if there are no PQEs in the PriorityQueue 'NoElements' is thrown
	//*if there are no 'index' PQEs in the PQ 'IndexOutOfBounds' is thrown
	const Element& operator[](int index) const;
	Element& operator[](int index);
	//an helper function for printing a PriorityQueue
	friend std::ostream& operator<<(std::ostream& os,
			const PriorityQueue<P, T>& pq) {
		pq.print(os);
		return os;
	}

	//interface functions:
	//inserts a new node to the PriorityQueue according to the parameters
	//returns an iterator which points at the inserted node
	//*if the given data already exists in PQ 'ElementAlreadyExists' is thrown
	Iterator insert(const P& priority, const T& data);
	//inserts a new node to the PriorityQueue according to the PQE
	//returns an iterator which points at the inserted node
	//*if the given data already exists in PQ 'ElementAlreadyExists' is thrown
	Iterator insert(const PriorityQueueElement<P, T>& pqe);
	//erases a node from the PriorityQueue according to the index
	//returns an iterator which points at the node next to the erased one
	//*if there are no PQEs in the PriorityQueue 'NoElements' is thrown
	//*if there are no 'index' PQEs in the PQ 'IndexOutOfBounds' is thrown
	Iterator erase(const Iterator& iter);
	//erases all of the nodes in bounds of the indexes from the PriorityQueue
	//returns an iterator which points at the node next to the erased one
	//*if the indexes are out of bounds 'IndexOutOfBounds' is thrown
	Iterator erase(const Iterator& from, const Iterator& to);
	//erases a node from the PriorityQueue according to the data
	//returns an iterator which points at the node next to the erased one
	//*if there are no PQEs in the PriorityQueue 'NoElements' is thrown
	//*if the data does not exist 'ElementDoesNotExist' is thrown
	Iterator erase(const T& data);
	//returns a reference to the top (with the greatest priority) PQE in the PQ
	//*if there are no PQEs in the PriorityQueue 'NoElements' is thrown
	const Element& top() const {
		return (*this)[0];
	}
	Element& top() {
		return (*this)[0];
	}
	//erases the top PQE in the PQ (the one with the greatest priority)
	//*if there are no PQEs in the PriorityQueue 'NoElements' is thrown
	void pop() {
		erase(begin());
	}
	//returns the amount of PriorityQueueElements in the PriorityQueue
	int size() const {
		return amount;
	}
	//checks if there are no PriorityQueueElements in the PriorityQueue
	bool empty() const {
		return amount == 0;
	}
	//prints all of the PriorityQueueElements in the PriorityQueue
	void print(std::ostream& os) const {
		print(os,begin(),end());
	}
	//prints all of the PQEs in bounds of the indexes from the constant PQ
	void print(std::ostream& os, const const_iterator& from,
			const const_iterator& to) const;
	//prints all of the PQEs which meet a given templative criteria from the PQ
	template<class F>
	void print(std::ostream& os) const;

	//special functions:
	//returns an iterator which points to the first Node of the PQ
	Iterator begin() {
		return first;
	}
	//returns a constant iterator which points to the first Node of the PQ
	const_iterator begin() const {
		return first;
	}
	//returns an iterator which points to the 'Null' Node (the PQ's end)
	Iterator end() {
		return NULL;
	}
	//returns a constant iterator which points to the 'Null' Node (the PQ's end)
	const_iterator end() const {
		return NULL;
	}

private:
	//the class'es fields:
	//the PriorityQueue's first node
	Node* first=NULL;
	//the amount of PriorityQueueElements in the PriorityQueue
	int amount=0;

	//helper functions:
	//clears the PriorityQueue
	void clear() {
		erase(begin(), end());
	}
	//returns the index of a PriorityQueueElement with the given data
	//*if it dosen't exist -1 is returned
	int getIndex(const T& data) const;
	//returns the index of a Iterator. If it doesn't exists in this priority
	//queue (or if it's end), it throws IndexOutOfBounds
	int getIndex(const_iterator it) const;
	//checks if a PriorityQueueElement with the given data exists in the PQ
	bool contains(const T& data) const {
		return (getIndex(data) != -1);
	}
	//check if two iterators make valid range (in this priority queue)
	//if not, throw IndexOutOfBounds
	void checkRange(const const_iterator& from,
			const const_iterator& to) const;
};

template<class P, class T>
bool PriorityQueueElement<P, T>::operator==(
		const PriorityQueueElement<P, T>& pqe) const {
	return (data == pqe.data && priority == pqe.priority);
}

template<class P, class T>
bool PriorityQueueElement<P, T>::operator!=(
		const PriorityQueueElement<P, T>& pqe) const {
	return !(*this == pqe);
}

template<class P, class T>
typename PriorityQueue<P, T>::Iterator&
		PriorityQueue<P, T>::Iterator::operator++() {
	if (current) {
		current = current->next;
	}
	return *this;
}

template<class P, class T>
typename PriorityQueue<P, T>::Iterator
		PriorityQueue<P, T>::Iterator::operator++(int) {
	Iterator iter(*this);
	++(*this);
	return iter;
}

template<class P, class T>
typename PriorityQueue<P, T>::Iterator&
		PriorityQueue<P, T>::Iterator::operator+=(unsigned num) {
	for (unsigned i = 0; i < num; i++) {
		++(*this);
	}
	return *this;
}

template<class P, class T>
typename PriorityQueue<P, T>::Iterator
		PriorityQueue<P, T>::Iterator::operator+(unsigned num) const {
	return Iterator(*this) += num;
}

template<class P, class T>
typename PriorityQueue<P, T>::const_iterator&
		PriorityQueue<P, T>::const_iterator::operator++() {
	if (current) {
		current = current->next;
	}
	return *this;
}

template<class P, class T>
typename PriorityQueue<P, T>::const_iterator
		PriorityQueue<P, T>::const_iterator::operator++(int) {
	const_iterator iter(*this);
	++(*this);
	return iter;
}

template<class P, class T>
typename PriorityQueue<P, T>::const_iterator&
		PriorityQueue<P, T>::const_iterator::operator+=(unsigned num) {
	for (unsigned i = 0; i < num; i++) {
		++(*this);
	}
	return *this;
}

template<class P, class T>
typename PriorityQueue<P, T>::const_iterator
		PriorityQueue<P, T>::const_iterator::operator+(unsigned num) const {
	return const_iterator(*this) += num;
}

template<class P, class T>
PriorityQueue<P, T>::PriorityQueue(const PriorityQueue<P, T>& pq) {
	for (auto& element : pq) {
		insert(element);
	}
}

template<class P, class T>
PriorityQueue<P, T>& PriorityQueue<P, T>::operator=(
		const PriorityQueue<P, T>& pq) {
	if (this == &pq) {
		return *this;
	}
	clear();
	for (auto& element : pq) {
		insert(element);
	}
	return *this;
}

template<class P, class T>
const PriorityQueueElement<P, T>&
		PriorityQueue<P, T>::operator[](int index) const {
	if (amount == 0) {
		throw NoElements();
	}
	if (index >= amount || index < 0) {
		throw IndexOutOfBounds();
	}
	return *(begin()+index);
}

template<class P, class T>
PriorityQueueElement<P, T>&
		PriorityQueue<P, T>::operator[](int index) {
	if (amount == 0) {
		throw NoElements();
	}
	if (index >= amount || index < 0) {
		throw IndexOutOfBounds();
	}
	return *(begin()+index);
}

template<class P, class T>
typename PriorityQueue<P, T>::Iterator
		PriorityQueue<P, T>::insert(const P& priority, const T& data) {
	if (contains(data)) {
		throw ElementAlreadyExists();
	}
	Node* node = new Node(priority, data);
	amount++;
	Node **current=&first;
	while (*current && (*current)->pqe.priority>=priority) {
		current=&((*current)->next);
	}
	node->next = *current;
	*current = node;
	return Iterator(node);
}

template<class P, class T>
typename PriorityQueue<P, T>::Iterator
		PriorityQueue<P, T>::insert(const PriorityQueueElement<P, T>& pqe) {
	return insert(pqe.priority, pqe.data);
}

template<class P, class T>
typename PriorityQueue<P, T>::Iterator
		PriorityQueue<P, T>::erase(const Iterator& iter) {
	if (amount == 0) {
		throw NoElements();
	}
	int index=getIndex(iter);
	amount--;
	Node **current=&first;
	for (int i=0;i<index;i++) {
		current=&((*current)->next);
	}
	Node *next=(*current)->next;
	delete *current;
	return *current=next;
}

template<class P, class T>
typename PriorityQueue<P, T>::Iterator
		PriorityQueue<P, T>::erase(const Iterator& from, const Iterator& to) {
	checkRange(from, to);
	Iterator iter(from);
	while (iter != to) {
		iter = erase(iter);
	}
	return to;
}

template<class P, class T>
typename PriorityQueue<P, T>::Iterator
		PriorityQueue<P, T>::erase(const T& data) {
	if (amount == 0) {
		throw NoElements();
	}
	if (!contains(data)) {
		throw ElementDoesNotExist();
	}
	return erase(begin()+getIndex(data));
}

template<class P, class T>
void PriorityQueue<P, T>::print(std::ostream& os,
		const const_iterator& from,const const_iterator& to) const {
	try {
		checkRange(from, to);
	} catch (IndexOutOfBounds) {
	}
	for (const_iterator iter(from);iter!=to;iter++) {
		os << *iter;
	}
	if (to!=end()) {
		os << *to;
	}
}

template<class P, class T> template<class F>
void PriorityQueue<P, T>::print(std::ostream& os) const {
	F function;
	for (auto& element : *this) {
		if (function(element.priority)) {
			os << element;
		}
	}
}

template<class P, class T>
int PriorityQueue<P, T>::getIndex(const T& data) const {
	int index=0;
	for (auto& element : *this) {
		if (element.data==data) {
			return index;
		}
		++index;
	}
	return -1;
}

template<class P, class T>
int PriorityQueue<P, T>::getIndex(const_iterator it) const {
	auto current=begin();
	for (int index=0;current!=end();++current,++index) {
		if (it==current) {
			return index;
		}
	}
	throw IndexOutOfBounds();
}

template<class P, class T>
void PriorityQueue<P, T>::checkRange(const const_iterator& from,
		const const_iterator& to) const {
	if (from==end()) {
		if (to==end()) {
			return;
		}
		throw IndexOutOfBounds();
	}
	if (to==end()) {
		getIndex(from);
		return;
	}
	if (getIndex(from)>getIndex(to)) {
		throw IndexOutOfBounds();
	}
}

}
#endif /* PRIORITY_QUEUE_H_ */
